package algorithm.leetcode.I401to600;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Q451 {

    public String frequencySort(String s) {
        // int[]保存s的字符索引和出现次数
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o2[1] == o1[1] ? s.charAt(o1[0])-s.charAt(o2[0]) : o2[1] - o1[1]);
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0)+1);
        }

        for (int i = 0; i < s.length(); i++) {
            pq.add(new int[]{i, map.get(s.charAt(i))});
        }
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) sb.append(s.charAt(pq.poll()[0]));
        return sb.toString();
    }

    public static void main(String[] args) {
        Q451 q451 = new Q451();
        System.out.println(q451.frequencySort("ereaaeedar"));
    }

}
